The present invention relates to the requirement for multiple blocks of information scheduled periodically to access a physical layer of a single channel. Specifically, the present invention relates to achieving efficient utilization of the physical layer of a single channel and the optimized scheduling access of a single channel.
In wireless communication systems, there may be multiple blocks of information from multiple sources required to be scheduled for periodic access of single channel. Due to constraints of the physical layer of the channel, such as limited transmission rate or power level, each block of information may need to be segmented into several segments, with each segment scheduled at a position for accessing the channel.
While scheduling the different sources of information, several requirements must be considered. The single channel is divided into multiple addresses or positions to which information segments are assigned or scheduled. As multiple sources of information have their associated information block segments scheduled along the channel positions, the scheduled information is considered multiplexed onto the channel. Therefore, conflicts of positions between different segments of information must be avoided, i.e., a channel position cannot be shared by segments of two different information blocks. Thus, the first requirement is that each position can be assigned to only one segment of information.
Second, since the repetition period required by each source of information is based on functions associated with the information, the different sources of information require different periods for accessing a single channel. For example, in 3G UMTS, a Broadcast Channel (BCCH) having System Information Blocks (SIBs) with different periods signifies various latency of system functions, such as Power Control or Cell Selection. Shorter repetition periods lead to shorter latency since User Equipment (UE) can receive system information faster than required to perform system functions. However, this requirement compromises efficient use of limited bandwidth of the channel. Shorter repetition periods also imply heavier loading to the single channel and limit the possibility to allocate the bandwidth for other usages.
Third, in order to maximize channel efficiency, unassigned positions on the channel should be kept to a minimum in order to maximize the utilization of the channel.
Fourth, segments of the same block of information should be scheduled as consecutively as possible, since information often cannot be read until all segments of the same source of information arrive at the receiver.
One solution to this problem has been to use a first come first service (FCFS) assignment method. In this method, the scheduler begins scheduling with a first source""s block of information. Once the first source of information is scheduled, the scheduler then assigns positions to the block of information of a second source of information on to the single channel. While scheduling the second source of information, the scheduler needs to avoid assigning channel positions that are already assigned to the first source""s block of information. Thus, while scheduling the subsequently scheduled blocks of information, the scheduler needs to keep track of all positions that are already assigned to previously scheduled blocks of information.
FIGS. 1A and 1B show an example in which three sources of information are scheduled to access a single channel, CHANNEL A. Three blocks of information, SOURCE 1, SOURCE 2, and SOURCE 3 are shown having varying segment counts and repetition periods. FIG. 1B shows the scheduling of the red, blue and green information segments to positions on CHANNEL A based on the segment counts and required repetition periods of SOURCE 1, SOURCE 2 and SOURCE 3. As evident in CHANNEL A shown in FIG. 1B, there are unassigned positions remaining after the scheduling of the SOURCE 1, SOURCE 2 and SOURCE 3 information blocks (8, 9, 18, 19, 20 . . . ). As more blocks of information with different segment count and repetition period constraints are added for scheduling on CHANNEL A, a scheduling method that does not compromise one or more of the above requirements becomes difficult to achieve.
Using the FCFS approach results in several compromises, such as segments belonging to the same source""s block of information cannot be scheduled consecutively since the solution does not reserve enough consecutive positions available that can satisfy information with large segment counts. This compromise is shown in FIG. 1B for SOURCE 3, as the green information segments are not scheduled consecutively on CHANNEL A. This delays the reading of the SOURCE 3 block of information as the receiver awaits for all segments of the information block to arrive. Also, due to the periodic nature of the scheduling, two sources of information may conflict with each other at some future position, thus creating the need to perform global searches each time an information segment is to be assigned to a position in order to avoid the possible conflict.
What is needed is a method and system that determines the required bandwidth for a given set of information blocks and that efficiently schedules information while optimizing for the above requirements.
The present invention comprises a method for multiplexed scheduling of information blocks from multiple sources on a single communication channel divided into multiple address positions. The information block from each source has a repetition period and is divided into a number of segments. Once the total number of positions on the channel to be scheduled are determined, positions are mapped in a non-sequential order corresponding to nodes in a binary tree, whereby each layer of the binary tree corresponds to a particular repetition period. The blocks of information are assigned in the order of ascending repetition period. The information segments of each block are scheduled to unassigned positions at the associated binary tree layer as well as to all corresponding child nodes.